package listNodePractice;

import java.util.PriorityQueue;

public class Class23 {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        // 虚拟头结点
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        // 优先级队列，最小堆
        PriorityQueue<ListNode> pq = new PriorityQueue<>(
                lists.length, (a, b)->(a.val - b.val));

        // 将 k 个链表的头结点加入最小堆
        for (ListNode head : lists) {
            if (head != null)
                pq.add(head);
        }

        while (!pq.isEmpty()) {
            // 获取最小节点，接到结果链表中
            ListNode node = pq.poll();
            p.next = node;
            if (node.next != null) {
                pq.add(node.next);
            }
            // p 指针不断前进
            p = p.next;
        }


        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        listNode4.next=listNode5;

        ListNode listNode11 = new ListNode(1);
        ListNode listNode33 = new ListNode(3);
        ListNode listNode77 = new ListNode(7);
        listNode11.next=listNode33;
        listNode33.next=listNode77;

        ListNode[] listNodes={listNode1,listNode11};

        System.out.println(listNodes.length);
        Class23 class23 = new Class23();
        ListNode listNode = class23.mergeKLists(listNodes);

        while (listNode!=null){
            System.out.println(listNode.val);
            listNode=listNode.next;
        }


    }

}
